#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>

using namespace std;
#define MM 100001
int main() {
  bool prime[MM];
  int i,j ,k;
  for (i = 2; i < MM; ++i) prime[i] = true;
  prime[0] = prime[1] = false;
  for (i = 2; i < MM; ++i) {
    if (!prime[i]) continue;
    int j = i+i;
    while (j < MM) prime[j] = false, j += i;
  }
  string s;
  int largest = 1;
  while (cin >> s) {
    if (s == "0") break;
    largest = 0;
    for (i = 0; i < s.size(); ++i) {
      if (s[i] == '0')continue;
      int num = 0;
      for (j = 0; j < 5 && j + i < s.size(); ++j) {
        num = (num*10) + (s[i+j]-'0');
//        cout << num << endl;
        if (prime[num]) largest = max (largest, num);
      }
    }
    cout << largest << endl;;
  } return 0;
}

